﻿//
//#include<iostream>
//#include <vector>
//#include<unordered_map>
//
//using namespace std;
//
//
//
//class Solution {
//public:
//
//    //递归结束条件：当前状态字符串⻓度与 2 * n 相等，记录当前状态并返回；
//
//    //剪枝
// 
//    //两种情况
//    //    1. 若此时左括号数量⼩于字符串总⻓度的⼀半，则在当前状态的字符串末尾添加左括号并继续递归，
//    //    递归结束撤销添加操作；
//    //    2. 若此时右括号数量⼩于左括号数量（右括号数量可以由当前状态的字符串⻓度减去左括号数量求
//    //    得），则在当前状态的字符串末尾添加右括号并递归，递归结束撤销添加操作；
//    vector<string> res;
//    string path;
//    int leftnums;
//    int rightnums;
//    vector<string> generateParenthesis(int n) {
//
//        dfs(n, 0);
//        return res;
//    }
//private:
//    void dfs(int n, int pos) {
//        const int totalLength = 2 * n;
//        if (pos == totalLength) {
//            res.push_back(path);
//            return;
//        }
//        // 尝试添加左括号
//        //合法结点，左括号数量 < n，一旦等于，就不能递归了，需要剪枝
//        if (leftnums < n) {
//            path.push_back('(');
//            leftnums++;
//            dfs(n, pos + 1);
//
//            path.pop_back();
//            leftnums--;
//        }
//        // 尝试添加右括号
//        //合法节点，右括号数量 < 左括号
//        if (rightnums < leftnums) {
//            path.push_back(')');
//            rightnums++;
//
//            dfs(n, pos + 1);
//
//            path.pop_back();
//            rightnums--;
//        }
//    }
//};